package 剑指offer;


import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;

/**
 * Created by lenovo】 on 2017/2/20.
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序
 */
public class IsPopOrder {

    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stackA = new Stack();
        ArrayList<Integer> arrayListA = asArrayList(pushA);
        Iterator<Integer> iterator = arrayListA.iterator();
        int lenA = popA.length;
        // 遍历popA
        for (int i = 0; i < lenA; i++) {
            int tmp = popA[i];
            // 判断arrayListA是否还存在元素
            // 不存在则在stackA进行出栈操作
            if (!iterator.hasNext()) {
                if (stackA.pop() == tmp) {
                    continue;
                } else {
                    return false;
                }
            }
            while (iterator.hasNext()) {
                // 如果不相等，则到栈内寻找
                int a = iterator.next();
                if (a != tmp) {
                    if (stackA.contains(tmp)) {
                        //在则出站，不等则返回false
                        if (stackA.pop() != tmp) {
                            return false;
                        }
                    } else {
                        stackA.push(a);
                        iterator.remove();
                    }
                } else {
                    // 如果相等则删除
                    iterator.remove();
                    break;
                }
            }
        }

        // 判断stackA是否还有元素
        if(!stackA.empty()) {
            return false;
        }
        return true;
    }

    public ArrayList<Integer> asArrayList(int[] arr) {
        int len = arr.length;
        ArrayList<Integer> arrayList = new ArrayList();
        for (int i = 0; i < len; i++) {
            arrayList.add(arr[i]);
        }
        return arrayList;
    }
}
